// 给定一个二叉树的根节点 root ，返回它的 中序 遍历。

#include<bits/stdc++.h>
using namespace std;

struct TreeNode
{
    /* data */
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){};
};

class Solution
{
private:
    /* data */
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr){
            return res;
        }
        stack<TreeNode*> sta;
        while(!sta.empty() || root){
            while(root){
                sta.push(root);
                root=root->left;
            }
            root=sta.top();
            sta.pop();
            res.emplace_back(root->val);
            root = root->right;
        }
        return res;
    }

};




int main(int argc, char const *argv[])
{
    TreeNode* root = new TreeNode(1);
    root->right=new TreeNode(2);
    root->right->left=new TreeNode(3);
    Solution s;

    vector<int> res = s.inorderTraversal(root);
    for(auto i:res){
        cout<<i<<" ";
    }

    delete root->right->left;
    delete root->right;
    delete root;
    return 0;
}
